iT邦幫忙

2021 iThome 鐵人賽

DAY 23
1
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 23

LeetCode 雙刀流:70. Climbing Stairs

  • 分享至 

  • xImage
  •  

70. Climbing Stairs

這是一個動態規劃的經典題目「爬樓梯」,這個題目根據規則利用「遞迴」其實蠻直覺的。只是遞迴在這個題目中會存在一些效能與重複計算的問題,所以我們試圖從這個例子中觀察遞迴的問題,並且引入一種稱為「動態規劃(Dynamic Programming,DP)」的方法。

先看一下題目描述

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

再搭配範例理解題目

  • Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
  • Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

本題需要求的是當走到 n 階樓梯時有多少種可能,每一次可以移動一步或兩步。

開始實作

在理解完題目與條件之後,那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程:

方法 ①:遞迴法

根據觀察之後,我們可以會發現「爬第 n 階樓梯的方法數」等於「爬上 n−1 階樓梯的方法數量」 + 「爬上 n−2 階樓梯的方法數量」。根據這樣的觀察與規則之後,很容易就會想到使用遞迴的解法,可以寫出以下的寫法:

f(n) = f(n-1) + f(n-2)

用 Python 實作一次

class Solution:
    def climbStairs(self, n: int) -> int:
        W = [0, 1, 2]
        if len(W) < n:
            W[n] = climbStairs(n - 2) + climbStairs(n - 1);

        return W[n];

也可以用 JavaScript 復刻一次

var climbStairs = function(n) {
    let W = [0, 1, 2];
    if (W.length < n){
        W[n] = climbStairs(n - 2) + climbStairs(n - 1);
    }

    return W[n];
};

方法 ②:動態規劃法

方法一採用遞迴的規則如下:

f(n) = f(n-1) + f(n-2)

這個題目使用遞迴會存在一個問題,就是每次計算 f(n) 之後,會去遞迴計算 f(n-1) + f(n-2)。相同的概念在計算 f(n-1) 會去計算 f(n-2) + f(n-3)、f(n-2) 會去計算 f(n-3) + f(n-4),以這個例子來看,f(n-3) 會同時在 f(n-1) 和 f(n-2) 重複計算。這樣一來,當 n 很大的時候就會有更多的值會再遞迴過程中重複計算。

因此這裡想法是能不能將剛剛的 f(n-3) 給記錄下來,而不用每一個遞迴過程都重複計算。所以我們想到的是將結果存在一個變數當中(而非每次都計算),將遞迴的過程暫存到一個變數中,如下:

dp[i] = dp[i - 1] + dp[i - 2]

用 Python 實作一次

class Solution:
    def climbStairs(self, n: int) -> int:
        W = [0, 1, 2]
        for i in range(3, n):
            W[i] = W[i - 2] + W[i - 1]
        return W[n]

也可以用 JavaScript 復刻一次

var climbStairs = function(n) {
    var W = [0, 1, 2];
    for (var i = 3; i <= n; i++) {
        W[i] = W[i - 2] + W[i - 1];
    }

    return W[n];
};

反思沉澱

本題的規則是「爬第 n 階樓梯的方法數」等於「爬上 n−1 階樓梯的方法數量」 + 「爬上 n−2 階樓梯的方法數量」,你有沒有覺得這個概念很熟悉?這其實一種稱為「費氏數列」或「斐波那契数列」(Fibonacci)的東西,每一個數回等於前兩個數的總和,這是資工系或是演算法中相當經典的問題。本題可以算是從費氏數列延伸出來的應用,因為相當生活化,並且可以同時使用到「遞迴」與「動態規劃」兩種解法。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目,適合作為你下一個嘗試的練習:


嗨,大家好!我是維元,一名擅長網站開發與資料科學的雙棲工程師,斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師,同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗,持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享,邀請你加入 訂閱 接收最新資訊。


上一篇
LeetCode 雙刀流:53. Maximum Subarray
下一篇
LeetCode 雙刀流:62. Unique Paths
系列文
LeetCode 雙刀流:Python x JavaScript30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

1
TD
iT邦新手 4 級 ‧ 2021-10-09 15:08:29

經典題啊!

WeiYuan iT邦新手 4 級 ‧ 2021-10-09 20:46:42 檢舉

我也覺得這題很好玩???

0
david1999
iT邦新手 5 級 ‧ 2024-02-03 22:42:14

Python
W[n] = climbStairs(n - 2) + climbStairs(n - 1);

list 應該不能直接給值,會出現下列錯誤
IndexError: list assignment index out of range
可以考慮用 append 改寫

我要留言

立即登入留言